package LeetCode;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName DataStructure
 * @Description: TODO
 * @date ${DAT}17:02
 */
public class interview39 {

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 2, 2, 2, 5, 4, 2};
        System.out.println(new interview39().majorityElement(arr));
    }

    public int majorityElement(int[] nums) {
        int len = nums.length;
        int result = 0;
        Map<Integer,Integer> map = new HashMap();
        for (int num : nums) {
            map.put(num,0);
        }
        for (int num : nums) {
            map.put(num,map.get(num)+1);
            if (map.get(num)>(len/2)){
                 result = num;
            }
        }
        return result;
    }
}
